package src.dp.bag01;

public class no474 {  // 1和0，装满背包最多有多少个物品

    /**
     * 1. dp数组下标含义：装满容量为 i 个 0、j个 1 的背包，最多有 dp[i][j] 件物品
     * 数组中每个元素相当于一个物品，每个物品重量是 x个0 + y个1
     * 2. 递推公式：dp[i][j] = max( dp[i][j], dp[i-x][j-y] +1 )
     * 3. 初始化数组：dp[0][0]=0
     * 4. 遍历顺序：先物品后背包，遍历背包时有 m 和 n 两个维度，因此遍历背包就有两层 for 循环
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {  //先遍历物品
            int x = 0, y = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') x++;
                if (c == '1') y++;
            }

            //后遍历背包，且必须倒序，背包重量有 m n 两个维度，所以两层for
            for (int i = m; i >= x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = Math.max( dp[i][j], dp[i-x][j-y] + 1 );
                }
            }

        }
        return dp[m][n];
    }

}
